home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / gmp-132.lha / gmp-1.3.2 / mpz_dmincl.c < prev    next >
C/C++ Source or Header  |  1993-05-19  |  5KB  |  173 lines
  1. /* mpz_dmincl.c -- include file for mpz_dm.c, mpz_mod.c, mdiv.c.
  2.  
  3. Copyright (C) 1991 Free Software Foundation, Inc.
  4.  
  5. This file is part of the GNU MP Library.
  6.  
  7. The GNU MP Library is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2, or (at your option)
  10. any later version.
  11.  
  12. The GNU MP Library is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with the GNU MP Library; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. /* THIS CODE IS OBSOLETE.  IT WILL SOON BE REPLACED BY CLEANER CODE WITH
  22.    LESS MEMORY ALLOCATION OVERHEAD.  */
  23.  
  24. /* If den == quot, den needs temporary storage.
  25.    If den == rem, den needs temporary storage.
  26.    If num == quot, num needs temporary storage.
  27.    If den has temporary storage, it can be normalized while being copied,
  28.      i.e no extra storage should be allocated.  */
  29.  
  30. /* This is the function body of mdiv, mpz_divmod, and mpz_mod.
  31.  
  32.    If COMPUTE_QUOTIENT is defined, the quotient is put in the MP_INT
  33.    object quot, otherwise that variable is not referenced at all.
  34.  
  35.    The remainder is always computed, and the result is put in the MP_INT
  36.    object rem.  */
  37.  
  38. {
  39.   mp_ptr np, dp;
  40.   mp_ptr qp, rp;
  41.   mp_size nsize = num->size;
  42.   mp_size dsize = den->size;
  43.   mp_size qsize, rsize;
  44.   mp_size sign_remainder = nsize;
  45. #ifdef COMPUTE_QUOTIENT
  46.   mp_size sign_quotient = nsize ^ dsize;
  47. #endif
  48.   unsigned normalization_steps;
  49.  
  50.   nsize = ABS (nsize);
  51.   dsize = ABS (dsize);
  52.  
  53.   /* Ensure space is enough for quotient and remainder. */
  54.  
  55.   /* We need space for an extra limb in the remainder, because it's
  56.      up-shifted (normalized) below.  */
  57.   rsize = nsize + 1;
  58.   if (rem->alloc < rsize)
  59.     _mpz_realloc (rem, rsize);
  60.  
  61.   qsize = nsize - dsize + 1;    /* qsize cannot be bigger than this.  */
  62.   if (qsize <= 0)
  63.     {
  64. #ifdef COMPUTE_QUOTIENT
  65.       quot->size = 0;
  66. #endif
  67.       if (num != rem)
  68.     {
  69.       rem->size = num->size;
  70.       MPN_COPY (rem->d, num->d, nsize);
  71.     }
  72.       return;
  73.     }
  74.  
  75. #ifdef COMPUTE_QUOTIENT
  76.   if (quot->alloc < qsize)
  77.     _mpz_realloc (quot, qsize);
  78.   qp = quot->d;
  79. #else
  80.   qp = (mp_ptr) alloca (qsize * BYTES_PER_MP_LIMB);
  81. #endif
  82.   np = num->d;
  83.   dp = den->d;
  84.   rp = rem->d;
  85.  
  86.   /* Make sure quot and num are different.  Otherwise the numerator
  87.      would be successively overwritten by the quotient digits.  */
  88.   if (qp == np)
  89.     {
  90.       np = (mp_ptr) alloca (nsize * BYTES_PER_MP_LIMB);
  91.       MPN_COPY (np, qp, nsize);
  92.     }
  93.  
  94.   count_leading_zeros (normalization_steps, dp[dsize - 1]);
  95.  
  96.   /* Normalize the denominator, i.e. make its most significant bit set by
  97.      shifting it NORMALIZATION_STEPS bits to the left.  Also shift the
  98.      numerator the same number of steps (to keep the quotient the same!).  */
  99.   if (normalization_steps != 0)
  100.     {
  101.       mp_ptr tp;
  102.       mp_limb ndigit;
  103.  
  104.       /* Shift up the denominator setting the most significant bit of
  105.      the most significant word.  Use temporary storage not to clobber
  106.      the original contents of the denominator.  */
  107.       tp = (mp_ptr) alloca (dsize * BYTES_PER_MP_LIMB);
  108.       (void) mpn_lshift (tp, dp, dsize, normalization_steps);
  109.       dp = tp;
  110.  
  111.       /* Shift up the numerator, possibly introducing a new most
  112.      significant word.  Move the shifted numerator in the remainder
  113.      meanwhile.  */
  114.       ndigit = mpn_lshift (rp, np, nsize, normalization_steps);
  115.       if (ndigit != 0)
  116.     {
  117.       rp[nsize] = ndigit;
  118.       rsize = nsize + 1;
  119.     }
  120.       else
  121.     rsize = nsize;
  122.     }
  123.   else
  124.     {
  125. #ifdef COMPUTE_QUOTIENT
  126.       if (rem == den || quot == den)
  127. #else
  128.       if (rem == den)
  129. #endif
  130.     {
  131.       mp_ptr tp;
  132.  
  133.       tp = (mp_ptr) alloca (dsize * BYTES_PER_MP_LIMB);
  134.       MPN_COPY (tp, dp, dsize);
  135.       dp = tp;
  136.     }
  137.  
  138.       /* Move the numerator to the remainder.  */
  139.       if (rp != np)
  140.     MPN_COPY (rp, np, nsize);
  141.  
  142.       rsize = nsize;
  143.     }
  144.  
  145.   qsize = rsize - dsize + mpn_div (qp, rp, rsize, dp, dsize);
  146.  
  147.   rsize = dsize;
  148.  
  149.   /* Normalize the remainder.  */
  150.   while (rsize > 0)
  151.     {
  152.       if (rp[rsize - 1] != 0)
  153.     break;
  154.       rsize--;
  155.     }
  156.  
  157.   if (normalization_steps != 0)
  158.     rsize = mpn_rshift (rp, rp, rsize, normalization_steps);
  159.  
  160.   rem->size = (sign_remainder >= 0) ? rsize : -rsize;
  161.  
  162. #ifdef COMPUTE_QUOTIENT
  163.   /* Normalize the quotient.  We may have at most one leading
  164.      zero-word, so no loop is needed.  */
  165.   if (qsize > 0)
  166.     qsize -= (qp[qsize - 1] == 0);
  167.  
  168.   quot->size = (sign_quotient >= 0) ? qsize : -qsize;
  169. #endif
  170.  
  171.   alloca (0);
  172. }
  173.